1777E - Edge Reverse - CodeForces Solution

// 2023-01-22
#include <bits/stdc++.h>
#define fastio                    \
	ios_base::sync_with_stdio(0); \
	cin.tie(0);
#define vi vector<int>
#define vl vector<long long>
#define vc vector<char>
#define vs vector<string>
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vp vector<pi>
#define vpl vector<pl>
#define ll long long
#define MAX 2147000000
#define MOD 1000000007
using namespace std;

int main(){
	fastio;
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        vector<vp> g(n + 1);
        for(int i{0}; i < m; ++i){
            int a, b, c;
            cin >> a >> b >> c;
            g[a].push_back({b, c});
        }
        int l{0}, r{(int)1e9};
        int ans{-1};
        while(l <= r){
            int mid{(l + r) / 2};
            vector<vi> g2(n + 1);
            for(int i{1}; i <= n; ++i){
                for(auto& j : g[i]){
                    g2[i].push_back(j.first);
                    if(j.second <= mid){                        
                        g2[j.first].push_back(i);
                    }
                }
            }  
            vi visited(n + 1);
            int root; 
            function<void(int)> dfs = [&](int cur){
                for(auto& i : g2[cur]){
                    if(visited[i] == 0){
                        visited[i] = 1;
                        dfs(i);
                    }
                }
                root = cur;
            };
            for(int i{1}; i <= n; ++i){
                if(!visited[i]){
                    visited[i] = 1;
                    dfs(i);
                }
            }
            vi ch(n + 1);
            ch[root] = 1;
            queue<int> Q;
            int cnt{0};
            Q.push(root);
            while(!Q.empty()){
                int x{Q.front()};
                Q.pop();
                cnt++;
                for(auto& i : g2[x]){
                    if(ch[i] == 0){
                        ch[i] = 1;
                        Q.push(i);
                    }
                }
            }
            if(cnt == n){
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        cout << ans << "\n";
    }
}